package simple;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/3/28 21:27
 */
public class No28_实现strStr {
    public static void main(String[] args) {
        Solution28 solution28 = new Solution28();
        String text = "A";
        String pattern = "AAAAA";
        int[] next = new int[pattern.length() + 1];


        int i = solution28.strStr(text, pattern);
        System.out.println();
    }
}

class Solution28 {
    //text:原字符串
    //pattern:待匹配串
    public int strStr(String text, String pattern) {
        //坑给填满
        if(pattern.length() == 0 ) return 0;
        if(text.length() == 0 || text.length() < pattern.length()) return -1;

        //KMP算法,极其烧脑,理解难度系数0.1
        int red = 0;
        int green = 0;
        int tLength = text.length();
        int pLength = pattern.length();
        int[] next = new int[pLength + 1];
        //初始化
        getNext(pattern, next);
        while (red < tLength && green < pLength) {
            //red 跟green位置字符比较
            if (text.charAt(red) == pattern.charAt(green)) {
                //相同
                red++;
                green++;
            } else {
                //不相同
                green = next[green];
                if (green == -1) {
                    red++;
                    green++;
                }
            }
        }
        //red >= 长度 || green >= 长度
        //额外条件...
        if (green <= pLength - 1) {
            return -1;
        } else {
            return red - green;
        }
    }

    //next数组的获取
    public void getNext(String pattern, int[] next) {
        //'递归'结束条件
        next[0] = -1;
        int green = 0;
        int red = -1;
        int pLength = pattern.length();
        while (green <= pLength - 1) {
            if (red == -1 || pattern.charAt(red) == pattern.charAt(green)) {
                red++;
                green++;
                next[green] = red;
            } else {
                red = next[red];//这个比较难理解,注意分析
            }
        }
    }

}

//public int strStr(String a, String b) {
//    return a.indexOf(b);
//}

//public int strStr(String a, String b) {
//    int aLength = a.length();
//    int bLength = b.length();
//    if (a.length() < b.length()) {
//        return -1;
//    } else if (a.equals("") && b.equals("")) {
//        return 0;
//    } else if (a.equals("")) {
//        return -1;
//    } else if (b.equals("")) {
//        return 0;
//    }
//    char bCheck = b.charAt(0); // body 的 'b'
//    for (int i = 0; i <= aLength - bLength; i++) {
//        char aChcek = a.charAt(i);
//        //轻度优化
//        if (aChcek == bCheck) {
//            String check = a.substring(i, i + bLength);
//            if (b.equals(check)) {
//                return i;
//            }
//        }
//    }
//    return -1;
//}

//public int strStr(String a, String b) {
//    int aLength = a.length();
//    int bLength = b.length();
//    if (a.length() < b.length()) {
//        return -1;
//    } else if (a.equals("") && b.equals("")) {
//        return 0;
//    } else if (a.equals("")) {
//        return -1;
//    } else if (b.equals("")) {
//        return 0;
//    }
//    for (int i = 0; i <= aLength - bLength; i++) {
//        String check = a.substring(i, i + bLength);
//        if (b.equals(check)) {
//            return i;
//        }
//    }
//    return -1;
//}
